package com.yxc.elastic.plugin.lcs;

public class LCSSimilarity {
    // 获取两个字符串数组的最长公共子序列（Longest Common Subsequence）相似度
    public static double getLCSSimilarity(String[] seq1, String[] seq2) {
        int m = seq1.length; // 第一个序列的长度
        int n = seq2.length; // 第二个序列的长度

        int[][] dp = new int[m + 1][n + 1]; // 创建动态规划表
        // 填充动态规划表
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (seq1[i - 1].equals(seq2[j - 1])) { // 如果当前元素相等
                    dp[i][j] = dp[i - 1][j - 1] + 1; // 在之前的基础上加1，表示找到一个公共元素
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]); // 否则取左上角的较大值
                }
            }
        }

        int lcsLength = dp[m][n]; // 最长公共子序列的长度
        double similarity = (2.0 * lcsLength) / (m + n); // 计算相似度
        return similarity;
    }

    public static void main(String[] args) {
        String[] a = {"BIO_get_host_ip","BIO_get_port","BUF_strdup","CRYPTO_free","CRYPTO_free","CRYPTO_free",
                "CRYPTO_free","DSO_global_lookup", "DSO_global_lookup","ERR_add_error_data","ERR_add_error_data",
                "ERR_add_error_data","ERR_put_error","ERR_put_error","ERR_put_error","ERR_put_error","ERR_put_error",
                "ERR_put_error","bind","bind","close","close","close","connect","listen","setsockopt",
                "socket","socket","strchr"};
        String[] b = {"CRYPTO_free","CRYPTO_malloc","ERR_put_error","ERR_put_error","EVP_DigestInit_ex",
                "EVP_DigestUpdate","EVP_MD_CTX_cleanup","EVP_MD_CTX_init","EVP_VerifyFinal","EVP_get_digestbyname",
                "OBJ_nid2sn","OBJ_obj2nid","OPENSSL_cleanse"};


        String[] srcCalleeList = {
            "CRYPTO_free", "CRYPTO_malloc", "ERR_put_error", "ERR_put_error", 
            "EVP_DigestInit_ex", "EVP_DigestUpdate", "EVP_MD_CTX_cleanup", 
            "EVP_MD_CTX_init", "EVP_VerifyFinal", "EVP_get_digestbyname", 
            "OBJ_nid2sn", "OBJ_obj2nid", "OPENSSL_cleanse"
        };
        // String[] calleeList = { "ASN1_INTEGER_new", "ASN1_INTEGER_set", "ERR_put_error", "TS_RESP_CTX_set_status_info" }; //0.1176470588235294;
        // String[] calleeList = { "ASN1_INTEGER_get", "ASN1_item_free", "ASN1_item_free", "ERR_put_error", "ERR_put_error", "ERR_put_error", "PKCS7_to_TS_TST_INFO" }; //0.2;
        // String[] calleeList = { "ERR_put_error", "X509V3_EXT_get_nid" }; //0.1333333333333333;

        String[] calleeList = { "ERR_put_error", "ERR_put_error", "ERR_put_error", "EVP_PKEY_size" }; //0.235294117647058;
        double lcsSimilarity = getLCSSimilarity(a, b);
        System.out.println("LCS相似度： " + lcsSimilarity);
    }
}


